/*
 * @lc app=leetcode.cn id=1713 lang=typescript
 *
 * [1713] 得到子序列的最少操作次数
 */

// @lc code=start
function minOperations(target: number[], arr: number[]): number {
  // 找到lcs中第一个大于target的值
  const binarySearch = (lcs: number[], target: number): number => {
    const m = lcs.length;
    // 数组为空或者target大于数组中的所有值
    if (m === 0 || target > lcs[m - 1]) {
      return m;
    }
    let l = 0;
    let r = m - 1;
    let mid: number;
    while (l < r) {
      mid = l + ((r - l) >> 1);
      if (lcs[mid] < target) l = mid + 1;
      else r = mid;
    }
    return l;
  };
  // 记录数字在target中的下标
  const m = target.length;
  const hash: Map<number, number> = new Map();
  for (let i = 0; i < m; i++) {
    hash.set(target[i], i);
  }
  // 计算2个数组间最长公共子序列
  const lcs = [];
  for (const num of arr) {
    if (hash.has(num)) {
      const idx = hash.get(num);
      const pos = binarySearch(lcs, idx);
      if (pos === lcs.length) {
        lcs.push(idx);
      } else {
        lcs[pos] = idx;
      }
    }
  }
  return m - lcs.length;
}
// @lc code=end
